//
// Created by denglibin on 2019/6/24 0024.
//

/************************************队列的顺序存储实现********************************************/
/**
 * 1、队列:一端进，另一端出；队列由两个参数决定，front(头),rear(尾)；
    头指针指向头一个元素，尾指针指向指向最后一个元素的下一存储单元；若数组长度为n，当元素个数为n-1时就认为队列已满。r指向最后一个空的元素空间。

    出队：头指针往上移动，

    入队：尾指针向上移动，故：静态队列只能是循环队列，不然出队的元素占用的空间
    永远无法重复利用。

    1）：队列的初始化:front,rear的值都是零、
    2）：队列非空：front代表的是队列的第一个元素,rear代表的是队列的最后一个元素的下个存储单元
    3)  ：队列空:front和rear的值相等，但不一定是零
    4）：动态队列：链表实现
         静态队列：数组实现

2、循环队列:
    出队：f = (f+1) % 数组长度
    入队：r = (r+1) % 数组长度

        +++++++++++++++++++++
        +		    +
        +		    +<----r
        +		    +
        +++++++++++++++++++++
        +		    +
        +	c	    +
        +		    +
        +++++++++++++++++++++
        +		    +
        +	b	    +
        +		    +
        +++++++++++++++++++++
        +		    +
 f ---> +	 a	    +
        +		    +
        +++++++++++++++++++++

    如何判断循环队列是否为空: 如果f == r 就一定为空
    如何判断队列已满：
        1）增加一个标志n记录队列元素的个数，当n = 数组长度-1时，就满了。
        2)if((r+1)%arr.length == f){
            队列已满
        }
        通常使用第二种
 * **/

#include <stdio.h>
#include <stdlib.h>

/**
 * 循环队列
 */
typedef struct array_queue
{
    int *data; //数组
    int limit; //队列容量
    int size;  //队列中元素个数
    int head;  //队首
    int tail;  //队尾
} ArrayQueue;

/**
 * 创建队列
 * @param limit
 * @return
 */
static ArrayQueue *createArrayQueue(int limit)
{
    ArrayQueue *queue = (ArrayQueue *)calloc(1, sizeof(ArrayQueue));
    int *data = (int *)calloc(limit + 1, sizeof(int)); //因为队尾指向最后一个元素的下一个位置，所以数组大小为limit+1
    queue->data = data;
    queue->size = 0;
    queue->limit = limit;
    queue->head = 0;
    queue->tail = 0;
}

/**
 * 队列是否满了
 * @param queue
 * @return
 */
static int isFull(ArrayQueue *queue)
{
    if ((queue->tail + 1) % (queue->limit + 1) == queue->head)
    {
        return 1;
    }
    return 0;
}

/**
 * 是否空
 * @param queue
 * @return
 */
static int isEmpty(ArrayQueue *queue)
{
    if (queue->head == queue->tail)
    {
        return 1;
    }
    return 0;
}

/**
 * 入队
 * @param queue
 * @param data
 */
static void enqueue(ArrayQueue *queue, int data)
{
    if (isFull(queue))
    {
        printf("queue is full\n");
        return;
    }
    queue->data[queue->tail] = data;
    queue->tail = (queue->tail + 1) % (queue->limit + 1);
    queue->size++;
}

/**
 * 出队
 * @param queue
 * @return
 */
static int dequeue(ArrayQueue *queue)
{
    if (isEmpty(queue))
    {
        printf("queue is empty\n");
        return -1;
    }
    int data = queue->head;
    queue->head = (queue->head + 1) % (queue->limit + 1);
    return data;
}
void freeQueue(ArrayQueue *queue)
{
    free(queue->data);
    free(queue);
}

int main22()
{
    ArrayQueue *queue = createArrayQueue(10);
    for (int i = 0; i < 12; i++)
    {
        enqueue(queue, i);
    }
    for (int i = 0; i < 12; i++)
    {
        printf("%d\n", dequeue(queue));
    }
    freeQueue(queue);
    return 0;
}
